1. Field of the Invention
The present invention relates to the filed of computer graphic imaging. Specifically, the present invention is an image-based triangle clipping mechanism that is particularly well suited for clipping triangles in combination with triangle imaging technologies such as a triangle scan-converter.
2. Description of Related Art
Triangles are the basic components of drawing complicated objects in computer graphics. Scientists working in this area have the experiences that most of the triangles drawn by graphics applications are smaller ones. An analysis of the distribution of the sizes and shapes of triangles in various graphics applications found that most of the triangles are small in these applications. More specifically, an 8×5 rectangle area can accommodate approximately 69% of all the triangles, a 12×8 area includes approximately 80% of all the triangles, and approximately 95% of the triangles can be held in a 40×30 area. Based on these values, a new image-based fast small triangle scan-conversion mechanism was developed by J. Cui and J. Chen, and reported in a paper entitled “Image-Based Fast Small Triangle Scan-Conversion” (sent to ACM Transactions on Graphics under review, 2003).
The image-based fast small triangle scan-conversion uses a width×height (e.g. 8×5) pixel matrix (rectangular pixel area) to save a triangle pattern, and therefore a pixel matrix array to save all possible small triangles patterns. An index scheme is used to reference the matrix array. When a program calls to draw a small triangle, an index is used to quickly locate the position of the triangle's pattern in the pixel matrix array and scan-convert it directly into the frame buffer. However, some of these triangles extend past the border of the viewing volume. Therefore, what is needed is a new 3D clipping mechanism which may be used with this image-based fast small triangle scan conversion mechanism.